﻿namespace Jsl.FxCop
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    /// <summary>
    /// Does a breadth first search of a graph.
    /// </summary>
    /// <typeparam name="TItem">The type of the item.</typeparam>
    public class BreadthFirstSearch<TItem>
    {
        #region Public Methods
        /// <summary>
        /// Searches starting at the specified item.
        /// </summary>
        /// <param name="firstItem">The first item.</param>
        /// <param name="itemVisitor">The item visitor.</param>
        /// <param name="getChildItems">Gets the child items.</param>
        /// <returns>The appropriate <see cref="SearchState"/>.</returns>
        public static SearchState Search(
            TItem firstItem,
            Func<TItem, SearchState> itemVisitor,
            Func<TItem, IEnumerable<TItem>> getChildItems)
        {
            return Search(new TItem[] { firstItem }, itemVisitor, getChildItems, null);
        }

        /// <summary>
        /// Searches the specified items.
        /// </summary>
        /// <param name="items">The items.</param>
        /// <param name="itemVisitor">The item visitor.</param>
        /// <param name="getChildItems">Gets the child items.</param>
        /// <returns>The appropriate <see cref="SearchState"/>.</returns>
        public static SearchState Search(
            IEnumerable<TItem> items,
            Func<TItem, SearchState> itemVisitor,
            Func<TItem, IEnumerable<TItem>> getChildItems)
        {
            return Search(items, itemVisitor, getChildItems, null);
        }

        /// <summary>
        /// Searches starting at the specified item.
        /// </summary>
        /// <param name="firstItem">The first item.</param>
        /// <param name="itemVisitor">The item visitor.</param>
        /// <param name="getChildItems">Gets the child items.</param>
        /// <param name="preventLoops"><c>true</c> if items should only be visited once.</param>
        /// <returns>The appropriate <see cref="SearchState"/>.</returns>
        public static SearchState Search(
            TItem firstItem,
            Func<TItem, SearchState> itemVisitor,
            Func<TItem, IEnumerable<TItem>> getChildItems,
            bool preventLoops)
        {
            return Search(new TItem[] { firstItem }, itemVisitor, getChildItems, preventLoops);
        }

        /// <summary>
        /// Searches the specified items.
        /// </summary>
        /// <param name="items">The items.</param>
        /// <param name="itemVisitor">The item visitor.</param>
        /// <param name="getChildItems">Gets the child items.</param>
        /// <param name="preventLoops"><c>true</c> if items should only be visited once.</param>
        /// <returns>The appropriate <see cref="SearchState"/>.</returns>
        public static SearchState Search(
            IEnumerable<TItem> items,
            Func<TItem, SearchState> itemVisitor,
            Func<TItem, IEnumerable<TItem>> getChildItems,
            bool preventLoops)
        {
            HashSet<TItem> visitedItems = preventLoops ? new HashSet<TItem>() : null;
            return Search(items, itemVisitor, getChildItems, visitedItems);
        }
        #endregion Public Methods

        #region Private Methods
        private static SearchState Search(
            IEnumerable<TItem> items,
            Func<TItem, SearchState> itemVisitor,
            Func<TItem, IEnumerable<TItem>> getChildItems,
            HashSet<TItem> visitedItems)
        {
            // Start with just the given items as the "parent" level.
            var parentsToVisit = items;

            // Walk through each item at the current level.
            while (true)
            {
                var parentOfChildrenToVisit = new List<TItem>();
                foreach (TItem item in parentsToVisit)
                {
                    if (visitedItems != null)
                    {
                        if (visitedItems.Contains(item))
                        {
                            // Skip the item since it has already been seen.
                            continue;
                        }
                        else
                        {
                            // Keep track of all the items we have visited.
                            visitedItems.Add(item);
                        }
                    }

                    // Visit the item.
                    switch (itemVisitor(item))
                    {
                        case SearchState.ContinueSearch:
                            parentOfChildrenToVisit.Add(item);
                            break;

                        case SearchState.SkipDescendants:
                            break;

                        case SearchState.StopSearch:
                            return SearchState.StopSearch;
                    }
                }

                // If there is nothing left to search then exit.
                if (parentOfChildrenToVisit.Count == 0)
                {
                    break;
                }

                // The new list of parents is the children from all the parents.
                parentsToVisit =
                    from parent in parentOfChildrenToVisit
                    from child in getChildItems(parent)
                    select child;
            }

            return SearchState.ContinueSearch;
        }
        #endregion Private Methods
    }
}